#!/usr/bin/env python
# -*- coding: utf-8 -*-
#author: João Caixinha

import math
import sys
sys.setrecursionlimit(2 ** 20) #Aproximadamente 64MB

from BinaryTree import BinaryTree 
     
class KDTree :
    
    
    '''
    Class K_D_Tree, representa a estrutura da k-dtree, permite adicionar nos, remover
    e encontrar o vizinho mais proximo
    '''
    def __init__(self, pList, mem):
        self.mem = mem
        self.__pList = []
        self.fillTree(pList)
        self.__root = self.__tree.N - 1

    '''
    __reservMem, cria a BinaryTree que ira guardar os pontos e chaves da kd-tree
    '''
    def __reservMem(self,pList):
        if type(pList[0]).__name__ == 'int':
            self.__bitSize = 'int'
        else:
            self.__bitSize = len(pList[0])

        self.__tree = None
        self.__tree = BinaryTree(self.mem)

    '''
    fillTree, recebe uma lista de pontos e cria a kd-tree
    '''
    def fillTree(self, pList):
        self.__pList = pList      
        if self.__reservMem(pList) != -1:
            self.__fillTree(None, pList, None, None,0) 
        else:
            return None
    
    '''
    __fillTree, cria a estrutura da arvore a partir de uma dada lista
    '''
    def __fillTree(self, top, pList, rightOrLeft, memPos, dep):
        if not pList:
            return -1      
            
        if self.__bitSize != 'int':
            axi = dep % self.__bitSize
        else:
            axi = 0
        self.__quickSort(pList, 0, len(pList) - 1, axi)
        med = int(math.floor(len(pList) / 2))

        if not memPos :
            x = self.__tree.malloc(pList[med]) 
            self.__tree.insert(x, top, rightOrLeft,1)
        else:
            x = memPos.pop(0)
            self.__tree.key[x] = pList[med]
            self.__tree.left[x] = None
            self.__tree.right[x] = None
            self.__tree.insert(x, top, rightOrLeft,0)
        
    
        altE = self.__fillTree(x, pList[:med], 1, memPos, dep + 1)  
   
        altD = self.__fillTree(x, pList[med + 1:], 0, memPos, dep + 1)
        self.__tree.BF[x] = (altD - altE) 
               
      
        if (altE < altD):            
            return altD + 1
        else:
            return altE + 1    

    '''
    adiciona um nó á kd-tree
    '''
    def addNode(self,node): 
       
        if(self.__bitSize == 'int') and type(node).__name__ != 'int':
            print 'Ilegal entry!'
            return -1
        elif(self.__bitSize != 'int') and self.__bitSize != len(node):
            print 'Ilegal entry!'
            return -1  
        self.__addNode(self.__root, node, 0)
        self.__pList.append(node)

        print 'add ' + str(node)
        

    '''
    removeNode, remove um nó da tabela, cria uma lista dos filhos, recria o ramo
    a partir do ponto que se pretende apagar, desta forma este deixa de pertencer ao ramo
    '''
    def removeNode(self, node):
#        try:
        if(self.__pList):
            self.__bit = -1
            pos = self.__findNode(self.__root, node, 0)
            if pos != None:
                '''
                encontra os filhos do nó
                '''
                nodes = []
                memPos = []
                self.__getChildrenKey(pos[0], nodes, memPos)
                nodes.pop(0)
                rem = memPos.pop()
                
                '''
                se o nó tiver filhos
                '''
                if(nodes):                    
                   
                    self.__fillTree(self.__tree.p[pos[0]], nodes, None, memPos, pos[1]) 
                else:
                    '''
                    se o nó não tiver filhos
                    '''
                    p = self.__tree.p[pos[0]]
                    if self.__tree.right[p] == pos[0]:
                        self.__tree.right[p] = None
                    elif self.__tree.left[p] == pos[0]:
                        self.__tree.left[p] = None
                  
                self.__tree.copyNode(rem)
                self.__pList.remove(node)
                self.__verifyBalance(self.__root,0)
                print 'Remove ( ' + str(node) + ' )'
            else:
                print "Node not in tree"
            pass
        else:
            print 'Tree is empty!'
#        except:
#            print 'Internal error!'


    '''
    __findNode, encontra a posição de memoria de um dado nó
    '''
    def __findNode(self, currentNode, node, dep):
        self.getNextBit()      
        
        if currentNode == None:
            return None       
        
        else:
            key = self.__tree.key[currentNode]
            if key == node:
                pos = currentNode,dep
            else:  
                '''
                A trabalhar com uma lista de tuplos
                '''
                if self.__bitSize != 'int':  
                    axi = dep % len(node)        
                    if  key[axi] < node[axi]:
                        pos = self.__findNode(self.__tree.right[currentNode], node, dep + 1)
                        if pos:
                            self.__tree.BF[currentNode] += 1 
                        pass
                    elif key[axi] > node[axi]:
                        pos = self.__findNode(self.__tree.left[currentNode], node, dep + 1)
                        if pos:
                            self.__tree.BF[currentNode] -= 1
                            
                    
                    elif key[axi] == node[axi]:
                        pos = self.__findNode(self.__tree.right[currentNode], node, dep + 1)
                        if pos != None:
                            self.__tree.BF[currentNode] += 1 
                            return pos
                        pos = self.__findNode(self.__tree.left[currentNode], node, dep + 1)
                        if pos:
                            self.__tree.BF[currentNode] -= 1
                else:
                    '''
                    A trabalhar com uma lista de inteiros
                    '''
                    if  key < node:
                        pos = self.__findNode(self.__tree.right[currentNode], node, 0)
                        if pos:
                            self.__tree.BF[currentNode] += 1 
                        pass
                    elif key > node:
                        pos = self.__findNode(self.__tree.left[currentNode], node, 0)
                        if pos:
                            self.__tree.BF[currentNode] -= 1 
                    
                    elif key == node:
                        pos = self.__findNode(self.__tree.right[currentNode], node, dep + 1)
                        if pos != None:
                            self.__tree.BF[currentNode] += 1 
                            return pos
                        pos = self.__findNode(self.__tree.left[currentNode], node, dep + 1)
                        if pos:
                            self.__tree.BF[currentNode] -= 1
                
        return pos
    '''
    __getChildrenKey, devolve uma lista das chaves de todos os nós filhos de
    um dados nó
    '''
    def __getChildrenKey(self, chid, keys, memPos):
        
        if(chid == None):
            return None
        else:
            key = self.__tree.key[chid]
            keys.append(key)
            memPos.append(chid)
            
        self.__getChildrenKey(self.__tree.right[chid], keys, memPos)
        self.__getChildrenKey(self.__tree.left[chid], keys, memPos)    

    '''
    __addNode, funcão para adicionar um nó
    '''
    def __addNode(self, currentNode, insert, dep): 
        if(self.__pList):             
            key = self.__tree.key[currentNode]

            '''
            A trabalhar com uma lista de tuplos
            '''
            if self.__bitSize != 'int':
                axi = dep % self.__bitSize
                if  key[axi] < insert[axi]:
                    if self.__tree.right[currentNode] == None: #lado direito
                        x = self.__tree.malloc(insert)
                        self.__tree.insert(x, currentNode, 0, 1)
                        self.__tree.BF[x] = 0
                    else:
                        self.__addNode(self.__tree.right[currentNode], insert, dep + 1) 
                        self.__tree.BF[currentNode] += 1   
                                            
                elif key[axi] >= insert[axi]: 
                    if self.__tree.left[currentNode] == None: #lado esquerdo
                        x = self.__tree.malloc(insert)
                        self.__tree.insert(x, currentNode, 1, 1)
                        self.__tree.BF[x] = 0
                    else:
                        self.__addNode(self.__tree.left[currentNode], insert, dep + 1)
                    self.__tree.BF[currentNode] -= 1

            else:
                '''
                A trabalhar com uma lista de inteiros
                '''
                if  key < insert:
                    if self.__tree.right[currentNode] == None: #lado direito
                        x = self.__tree.malloc(insert)
                        self.__tree.insert(x, currentNode, 0, 1)
                        self.__tree.BF[x] = 0
                    else:
                        self.__addNode(self.__tree.right[currentNode], insert,0) 
                        self.__tree.BF[currentNode] += 1   
                                            
                elif key >= insert: 
                    if self.__tree.left[currentNode] == None: #lado esquerdo
                        x = self.__tree.malloc(insert)
                        self.__tree.insert(x, currentNode, 1, 1)
                        self.__tree.BF[x] = 0
                    else:
                        self.__addNode(self.__tree.left[currentNode], insert,0)
                    self.__tree.BF[currentNode] -= 1
                        
            
            self.__verifyBalance(currentNode, dep)
        else:
            print 'Tree is empty!'
    
    ''' verifica se o nó esta balanceado'''
    def __verifyBalance(self, node, dep):
        BF = self.__tree.BF[node]
        if  BF < -1 or BF > 1:
            nodes = []
            memPos = []
                       
            self.__getChildrenKey(node, nodes, memPos)
            top = self.__tree.p[node]      
            if not top:
                self.__bit = -1          
            self.__fillTree(top, nodes, None, memPos, dep)
            
            #print '|    reBalance    |'
        pass

    '''
    findNearst, calcula qual o ponto mais proximo do ponto 
    indicado, calculado a menor norma 
    '''
    def findNearst(self,point):
        distance = [sys.maxint, None]
        self.__nearst(self.__root, point,distance,0)

        return distance[1:]


    '''
    __nearst, precorre os nós da arvore, verifica qual o 
    que tem menor distancia do ponto dado,actualiza a lista da distancia,
    caso exista mais do que um ponto com a menor distancia, adiciona á lista
    currentNode - e o nó atual
    point - o ponto a ser comparado, 
    distance - distancia mais pequena encontrada
    dep - prefundidade
    '''
    def __nearst(self, currentNode, point, distance, dep):
        if currentNode == None:
            return distance
        else:
            if  self.__tree.key[currentNode] < point:
                self.__nearst(self.__tree.right[currentNode], point, distance, dep + 1)
            elif self.__tree.key[currentNode] > point or self.__tree.key[currentNode] == point:
                self.__nearst(self.__tree.left[currentNode], point, distance, dep + 1)                   
            
            pDistance = self.__norm(currentNode,point)
            if (pDistance < distance[0]):
                if len(distance) > 2:
                    while(len(distance) > 2):
                        distance.pop()
                distance[0] = pDistance
                distance[1] = self.__tree.key[currentNode]
                
            elif(pDistance == distance[0]):
                distance.append(self.__tree.key[currentNode])
                
        
    '''
    __norm, calcula a norma entre dois pontos
    currentNode - ponto atual
    point - ponto de comparacao
    '''
    def __norm(self,currentNode,point):
        norm = 0
        key = self.__tree.key[currentNode]
        if self.__bitSize != 'int':
            for k in range(0,self.__bitSize):
                norm +=((key[k] - point[k])**2)        
            return math.sqrt(norm)
        else:
            norm = (key - point)**2
            return math.sqrt(norm)

    '''
    __quickSort, ordena os valores de uma lista,
    eficiencia OnLog(n)
    pior caso On
    '''
    def __quickSort(self,A,p,r, axi):
        if p < r:
            q = self.__partition(A,p,r, axi)
            self.__quickSort(A,p,q - 1, axi)
            self.__quickSort(A,q + 1, r, axi)
    '''
    __partition, ordena uma partição da lista
    '''    
    def __partition(self, A, p, r, axi):
        x = A[r]
        i = p - 1
        for j in range(p,r):
            if self.__bitSize == 'int':
                if A[j] <= x:  
                    i = i + 1
                    A[i], A[j] = A[j], A[i]              
            else:
                if A[j][axi] <= x[axi]:
                    i = i + 1
                    A[i], A[j] = A[j], A[i]
        A[i + 1], A[r] = A[r], A[i + 1]
        return i + 1
        
    def __str__(self):
        lista = []
        self.__getStr(self.__tree.N - 1, lista, 0,'-')
        s = ''
        for x in lista:
            s += self.__addToStr(x[0], x[1], x[2],x[3])
        return s
    
    '''
    __addToStr, adiciona uma linha na string que representa a class,
    '  ' * a profundidade do nó mais a chave 
    '''
    def __addToStr(self,node, dep,ori,pos):
        s = ''
        space = ''
        if self.__bitSize != 'int':
            for x in range(0,self.__bitSize):
                space += '    '
        else:
            space += '      '
        for x in range(0, dep):
            s += space
        if self.__bitSize == 'int':
            s += ori + '(' + str((node)) + ')\n'
        else:
            s += ori + str((node)) + '\n'
        return s
    
    '''
    __getStr, devolve uma lista com as chaves de cada nó, mais a orientação de cada um em relação
    ao pai e a sua perfundidade.
    '''           
    def __getStr(self, node, lista, dep, ori):        
        if node != None:            
            self.__getStr(self.__tree.right[node], lista, dep + 1,'/')
            lista.append((self.__tree.key[node], dep,ori,node))       
            self.__getStr(self.__tree.left[node], lista, dep + 1,'\\')

    '''
    __getAll, devolve uma lista com todos as chaves na arvore
    '''
    def __getAll(self, node, lista):        
        if node != None:            
            self.__getAll(self.__tree.right[node], lista)
            lista.append(self.__tree.key[node])       
            self.__getAll(self.__tree.left[node], lista)
        

    '''
    printAdressTable, imprime a tabela de endereços de cada nó
    '''
    def printAdressTable(self):
        print 'Adress Table\n' + str(self.__tree) + '\nHeadPos: ' + str(self.__tree.head) + '\ntop: ' + str(self.__tree.apontadores_memoria.top)




